﻿using System;

namespace Searches
{
    public static class SearchExtensions
    {
        public static void InsertionSort(this int[] array)
        {
            array.InsertionSort(0, array.Length);
        }

        private static void InsertionSort(this int[] array, int start, int seed)
        {
            for (int i = start; i < seed; i++)
            {
                int newElement = array[i];
                int location = i - 1;
                while (location >= start && array[location] > newElement)
                {
                    array[location + 1] = array[location];
                    location--;
                }
                array[location + 1] = newElement;
            }
        }

        public static void BubbleSearch(this int[] array)
        {
            int numberOfPairs = array.Length;

            bool swappedElements = true;
            while (swappedElements)
            {
                --numberOfPairs;
                swappedElements = false;
                for (int i = 0; i < numberOfPairs; i++)
                {
                    if (array[i] > array[i + 1])
                    {
                        int temp = array[i];
                        array[i] = array[i + 1];
                        array[i + 1] = temp;

                        swappedElements = true;
                    }
                }
            }
        }

        public static void MergeSort(this int[] array)
        {
            array.MergeSort(0, array.Length - 1);
        }

        private static void MergeSort(this int[] array, int first, int last)
        {
            if(first < last)
            {
                int middle = (first + last)/2;
                MergeSort(array, first, middle);
                MergeSort(array, middle + 1, last);
                MergeArrays(array, first, middle, middle + 1, last);
            }
        }

        private static void MergeArrays(int[] array, int start1, int end1, int start2, int end2)
        {
            int finalStart = start1;
            int finalEnd = end2;

            int[] merged = new int[finalEnd - finalStart + 1];

            int indexC = 0;
            while (start1 <= end1 && start2 <= end2)
            {
                if(array[start1] < array[start2])
                {
                    merged[indexC] = array[start1];
                    ++start1;
                }
                else
                {
                    merged[indexC] = array[start2];
                    ++start2;
                }
                ++indexC;
            }

            if(start1<=end1)
            {
                for (int i = start1; i <= end1; i++)
                {
                    merged[indexC] = array[i];
                    ++indexC;
                }
            }
            else
            {
                for (int i = start2; i <= end2; i++)
                {
                    merged[indexC] = array[i];
                    ++indexC;
                }
            }

            indexC = 0;
            for (int i = finalStart; i <= finalEnd; i++, indexC++)
            {
                array[i] = merged[indexC];
            }
        }

        public static void QuickSort(this int[] array)
        {
            array.QuickSort(0, array.Length);
        }

        private static void QuickSort(this int[] array, int first, int last)
        {
            if(first < last)
            {
                int pivot = PivotArray(array, first, last);
                array.QuickSort(first, pivot);
                array.QuickSort(pivot + 1, last);
            }
        }

        private static int PivotArray(int[] array, int first, int last)
        {
            int pivotValue = array[first];
            int pivotPoint = first;
            for (int index = first+1; index < last; index++)
            {
                if(array[index]<pivotValue)
                {
                    ++pivotPoint;
                    int temp = array[pivotPoint];
                    array[pivotPoint] = array[index];
                    array[index] = temp;
                }
            }

            int temp1 = array[first];
            array[first] = array[pivotPoint];
            array[pivotPoint] = temp1;

            return pivotPoint;
        }
    }
}